
\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{listings}
\usepackage{graphicx}

\def\udcs{} %Здесь автор определяет УДК своей работы
\def\mscs{} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{1}
\tolerance=1000

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}
\newtheorem{remark}{Замечание}
\newtheorem{con}{Гипотеза}
\newtheorem{openproblem}{Открытая проблема}

 
\def\logo{{\bf S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\top
     {
  \vbox{
     \noindent
     \hspace{80mm}\raisebox{1ex}{}

     \vspace{5mm}

     \begin{center}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it  \hspace{65mm}{\rm\small \udcs}}
     \newline
  }%\vbox
}

\begin{document}

\thispagestyle{empty}

\title{Eertree: an efficient data structure for processing palindromic factors in strings} 
\author{{Mikhail Rubinchik \\Ural Federal University}}%
\address{}%
\email{}%



\top \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. }
We propose a new linear-size data structure which provides a fast access to all palindromic factors of a string or a set of strings. This structure inherits some ideas from the construction of both suffix trie and suffix tree. Using this structure, we present simple and unified proofs for a number of problems concerning palindromes.

\noindent{\bf Keywords:} palindromic tree, string data structure, suffix tree.
 \end{quote}
}


%\textbf{Введение}
\textbf{Introduction}



Palindromes are among the most popular objects in stringology.
They have been being actively developed both in theory of formal languages and combinatorics on words during last decades.
Recall than palindrome is a string $w = a_1a_2\ldots a_n$ which is equal to its mirrored image $w = a_n\ldots a_2a_1$.
%Палиндромы являются одним из самой популярной особенностью в строках. В последние десятилетия и в теории формальных языков и в комбинаторики слов они активно изучаются. Напомним, что палиндромом называется строка $w = a_1a_2\ldots a_n$, совпадающая со своим зеркальным образом $w = a_n\ldots a_2a_1$.

Many algorithms study internals of palindromes in strings.
It is possible to highlight palindrome searching algorithms (\cite{Manacher}, \cite{DJP}, \cite{KoRuSh}, \cite{GPR}) and
palindrome decomposition algorithms (\cite{KoRuSh2}, \cite{Fici}).
We are introducing the <<palindromic tree>> data structure which will simplify solutions to both mentioned above problems as well as solutions
to other problems in this area significantly.
%Множество алгоритмов изучают внутреннее устройство подпалиндромов в строках. Среди них можно особенно выделить поиск подпалиндромов (\cite{Manacher}, \cite{DJP}, \cite{KoRuSh}, \cite{GPR}) и разбиение на палиндромы (\cite{KoRuSh2}, \cite{Fici}). В данной работе мы приведем структуру данных <<дерево палиндромов>>, которая существенно упростит решения этих двух задач и многих других в данной области.

In the first section of this paper we will introduce a simple online algorithm for searching subpalindromes.
In the second section we will highlight the most important details of the algorithm and generalize it.
As a result we will introduce the new effective data structure for processing of subpalindromes of a string.
In the third section we will discuss applicability of the palindromic tree for various famous problems.
We will show how much the palindromic tree simplifies these problems.
In the fourth section we will consider problems involving subpalindromes of several strings at once.
In the fifth and sixth sections we will discuss how to improve the palindromic tree to get a good unamortized complexity.
This improvement will allow us to solve persistent problems and problems with rollbacks involving subpalindromes.
In the seventh section we will introduce new solutions for $k$-palindromes decomposition and minimal decomposition problems.
%В первой главе данной работы мы приведём простой алгоритм поиска подпалиндромов онлайн. Во второй главе выделим основные идеи этого алгоритма и обобщим. В результате получим новую эффективную структуру данных по работе с подпалиндромами строки. Третья глава будет посвящена обсуждению применяемости дерева палиндромов в различных известных задачах. Мы наглядно увидим, как дерево палиндромов упрощает решение во многих задачах. Четвертая глава рассматривает ситуацию, когда нужно решать задачи о подпалиндромах сразу для нескольких строк. В пятой и шестой главах мы обсудим, как получить дерево с хорошей чистой (неамортизированной) оценкой для дерева палиндромов. Это даст нам возможность решать задачи обработки подпалиндромов с откатами и персистентные задачи. Седьмая глава содержит новое решение задачи о разбитии на $k$ палиндромов и о минимальном разбиении. 



\section{Введение в дерево палиндромов}
В данной главе мы введём интерфейс новой структуры данных, затем опишем граф, который его реализует, после чего подробней изучим структуру этого графа, а также обсудим некоторые технические аспекты решения.

\subsection{Определения и обозначения}

В данной работе мы будем называть подпалиндромом подстроку-палиндром строки. Будем называть чётными (нечётными) палиндромами палиндромы с чётной (нечётной) длиной. Центром подпалиндрома будем называть число $(l + r) / 2$, где $l, r$~--- позиции его концов, а радиусом палиндрома половину его длины округлённую вверх.
Также нам понадобятся термины: суффикс-палиндром и префикс-палиндром~--- это, соответственно, суффикс и префикс, являющиеся палиндромами.

Бором будем называть корневое дерево, каждое ребро которого помечено символом, причём из каждой вершины в её детей выходящие рёбра помечены разными буквами. Также в боре некоторые вершины помечены как терминальные.

\subsection{Интерфейс структуры данных}

В самой базовой версии мы имеем всего один вид запроса : \\
addLetter(c)~--- функция, которая приписывает к концу строки символ с и соответствующим образом обновляет дерево палиндромов и сообщает нам число новых палиндромов, которые появились в строке (т.е. 0, либо 1).

Это самая базовая часть структуры, мы рассмотрим множество различных модификаций в следующих главах.

\subsection{Предложение по построению структуры}

В дальнейшем мы будем опираться на следующий  важный факт.
\begin{lemma}(\cite{DJP}). При дописывании символа в конец строки, в ней появляется не более одного нового палиндрома, причем новым может быть только максимальный собственный суффикс полученной строки.
\end{lemma}

Мы будем хранить ориентированный граф. Каждая вершина графа будет соответствовать некоторому подпалиндрому нашей строки, причём одинаковым подпалиндромам соответствует одна вершина, а разным~--- разные.  Значит, число вершин будет обозначать число различных подпалиндромов строки. В каждой вершине мы будем хранить длину палиндрома, который ей соответствует. Далее мы будем отождествлять эти понятия, т.е. использовать одну переменную одновременно в двух смыслах (и как строку и как вершину дерева). Каждое ребро будет помечено символом алфавита, из каждой вершины не будет выходить двух ребер, помеченных одинаковыми символами. Для хранения ребер в каждой вершине мы будем использовать словарь с дополнительной информацией, который по символу алфавита будет возвращать номер вершины, в которую ведёт ребро, помеченное данным символом. Например, такой словарь можно реализовать с помощью бинарного сбалансированного дерева поиска. Помимо рёбер в нашем графе будут суффиксные ссылки.

Из вершины $A$ в вершину $B$ будет вести ребро, помеченное символом $x$, если $B = xAx$. Суффиксная ссылка будет вести из $A$ в $B$, если $B$ является длиннейшим собственным суффикс-палиндромом $A$. В [1] доказано, что при приписывании символа появляется не более одного нового подпалиндрома, а значит не более одной новой вершины в графе. Будем поддерживать следующий инвариант: если между вызовами методов структуры две вершины должны иметь между собой ребро (или суффиксную ссылку), то они его имеют. В таком случае на каждом шаге при появлении новой вершины могут появиться рёбра/ссылки только инцидентные этой вершине. 

\begin{lemma}
В вершину не может входить более одного ребра. 
\end{lemma}

\proof
Несложно видеть, что любое ребро помечено символом, которая совпадает с первым символом палиндрома, в которую оно ведёт. Значит все входящие рёбра помечены одним символом. Пусть в некоторую вершину С входит хотя бы два ребра (пусть они ведут из вершин $A$ и $B$), значит оба ребра помечены одинаковыми символами (пусть $x$). Значит $C = xAx = xBx$, следовательно $A = B$, что противоречит построению графа. 
\qed

Из каждой вершины выходит одна суффиксная ссылка и входит одно ребро. Значит при приписывании символа (в случае, когда появилась новая вершина) мы должны построить ровно одно ребро и одну суффиксную ссылку. Опишем алгоритм создания вершины и инцидентных ей ребра и суффиксной ссылки. 

Пусть у нас есть строка $S$. К ней приписали символ $a$. Получили строку $Sa$. Рассмотрим её максимальный суффикс-палиндром. Пусть он равен $P$. Раз $P$~--- суффикс $Sa$ и палиндром, то его можно представить в виде $P = aQa$. А это значит, что $aQ$ является суффиксом $S$, причём $Q$~--- палиндром. Значит поиск максимального суффикс-палиндрома строки $Sa$ равносилен поиску самого длинного суффикс-палиндрома в $S$, которому предшествует $a$. Будем перебирать все суффикс-палиндромы строки $S$ в порядке убывания длины, пока не встретим такой, которому предшествует $a$. Таким образом мы нашли $Q$. Из $Q$ мы можем перейти по ребру с меткой $a$ и попасть в вершину $aQa = P$. Если такого ребра нет, то $P$~--- это новый подпалиндром, иначе он уже встречался в строке. Длина $aQa$ очевидно вычисляется из длины $Q$. В $aQa$ входит одно ребро из $Q$ (по $a$). 

Осталось провести суффиксную ссылку. Выше мы описали алгоритм нахождения вершины в графе, отвечающей за максимальный суффикс-палиндром (по предыдущему максимальному). Аналогично можно получать второй по величине суффикс-палиндром (по предыдущему второму по величине). Разница только в том, что здесь мы будем спускаться по суффиксным ссылкам не только пока не встретим символ $а$, но и ещё пока наша длина больше максимального суффикс-палиндрома (уже найденного). Таким образом, мы теперь умеем поддерживать и создавать максимальный и второй по величине суффикс-палиндромы (создавать нужно только максимальный, второй создан когда-то ранее). 

Оценим асимптотику работы алгоритма. На каждом шаге мы проверяем наличие ребра из $Q$ с меткой $a$ за $O(\log|\Sigma|)$. Оценим число переходов по графу. На каждом шаге происходит ровно один переход по ребру (всего $n$) и ноль или более переходов по суффиксным ссылкам. Переход по ссылке сдвигает левую границу максимального суффикс-палиндрома вправо, а переход по ребру~--- влево на единицу. Значит, число переходов по ссыкам можно оценить сверху числом $2n$. Эти же свойства верны и для второго по величине суффикс-палиндрома.

Таким образом общая асимптотика алгоритма $O(n\log|\Sigma|)$. 

\subsection{Внутреннее устройство структуры} 

Для инициализации описанного выше построения нам понадобятся две фиктивные вершины, вершина <<0>> длины 0 и вершина <<-1>> длины -1.

Суффиксные ссылки из обеих вершин будут вести в вершину <<-1>>. Рёбра из <<-1>> будут вести в односимвольные строки. Рёбра из вершины <<0>> будут вести в двухсимвольные. Ссылки из односимвольных вершин будут вести в вершину <<0>>. 

Назовём вершину, которой соответствует чётный (нечётный) палиндром, чётной (соответственно, нечётной).

Теперь изучим, как именно устроен граф внутри нашей структуры. Если из вершины А в вершину В ведёт ребро, то длина В на 2 больше длины А. 
Что влечёт :


\begin{remark}
Из чётных вершин графа не достижимы нечётные и наоборот.
\end{remark}


\begin{remark}
Граф не имеет циклов. 
\end{remark}

Из замечаний выше следует, что граф состоит из двух не связанных друг с другом направленных деревьев, с корнями в вершинах <<0>> и <<-1>> соответственно.

Легко видеть, что дерево с корнем в вершине <<0>>~--- это бор всех правых половин чётных палиндромов, а дерево с корнем в <<-1>>~--- это бор всех правых половин (включая центр) нечётных палиндромов.

Т.е. в итоге наш граф~--- это просто два независимых бора. Но теперь мы должны вспомнить о суффиксных ссылках. К примеру, строка abaaba является чётным палиндромом, наибольший её суффикс-палиндром~--- это строка aba, которая является нечётным палиндромом. А значит суффиксная ссылка ведёт из одного бора в другой. Такие ссылки будем называть \textbf{перекрёстными}. 


\begin{remark}
Суффиксная ссылка всегда уменьшает длину вершины (за исключением вершины <<-1>>). А значит, единственным циклом из суффиксных ссылок является петля на <<-1>>. 
\end{remark}


Назовем суффиксным путем последовательность вершин, в которой из каждой вершины в следующую (если такая есть) ведёт суффиксная ссылка.

Из любой вершины существует суффиксный путь в -1. Следовательно, верна

\begin{lemma}
Граф, образованный вершинами исходного графа и обращёнными суффиксными ссылками, является направленным деревом c петлёй на корне. 
\end{lemma}

Будем называть описанный граф и множество суффиксных ссылок в нём\textbf{деревом палиндромов}.
Для дальнейшей работы нам понадобятся обозначения. Вся информация  о графе, включая дополнительную информацию для конкретных задач, хранится в его вершинах; величину $x$, хранимую в вершине $v$, мы будем обозначать через $x[v]$. Например, $len[v]$~--- длина $v$, $link[v]$~--- суффиксная ссылка из $v$, $go[v]$~--- словарь, в котором $go[v][c]$ соответствует номеру вершины, в которую ведёт ребро из $v$ по символу $c$.

\begin{remark}
Мы можем запретить перекрёстные суффиксные ссылки. Т.е. из каждой вершины вести ребро в максимальный суффикс-палиндром той же чётности. Тогда получим две абсолютно независимые структуры. Будем называть их дерево нечётных палиндромов (odd palindromic tree) и дерево чётных палиндромов (even palindromic tree).
\end{remark}

\begin{remark}
Заметим, что в дальнейшем у нас будут появляться и другие (вспомогательные) рёбра, а также в вершинах будет храниться различная дополнительная информация. В таком случае мы эту структуру будем называть деревом палиндромов с дополнительной информацией или модифицированным деревом палиндромов. 
\end{remark}

\subsection{Сравнение с суффиксными структурами данных}
Суффиксные структуры данных позволяют хранить информацию о всех подстроках данной строки. Если мы возьмём все суффиксы строки и сложим их в бор, то получим структуру, занимающую $O(n^2)$ памяти. В строковых алгоритмах эту проблему решают разными способами. Два довольно популярных из них заключаются в сжатии такого бора: удалить вершины степени два (сконкатенировав метки рёбер) и получить суффиксное дерево (suffix tree), либо объединить эквивалентные вершины и получить суффиксный автомат (DAWG).

В дереве палиндромов хранятся все подпалиндромы строки (т.е. часть подстрок), а их, как известно, всего $O(n)$. Поэтому структура уже изначально требует всего $O(n)$ памяти и не нуждается в сжатии. А значит, дерево палиндромов можно считать одновременно и аналогом суффиксного дерева и суффиксного автомата для всех подпалиндромов строки. 

\subsection{Построение дерева в оффлайне}
В строковых задачах часто помимо решения онлайн интересным является решение оффлайн для случая, когда алфавит является множеством целых положительных чисел $[1..n^c]$, где $c$~--- некоторая константа. 

В таком случае мы можем заранее за линейное время построить для строки суффиксный массив (\cite{PSW}) и массив радиусов палиндромов (с помощью алгоритма Манакера). 

1. Начнём с Манакера, получим два массива радиусов. \\

2. Посчитаем максимальный и второй по величине суффикс-палиндромы. \\
Заведём для этого три переменные: $R, L, L'$. Между итерациями алгоритма будем поддерживать следующий инвариант: $S[L..R]$~--- максимальный суффикс-палиндром строки $S[1..R]$, а $S[L'..R]$~--- второй по величине среди суффикс-палиндромов $S[1..R]$. 

\lstset{frame=tb,
  language=Pascal,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle=\ttfamily,
  numbers=none,
  keywordstyle=\bf,
  breaklines=true,
  breakatwhitespace=true
  tabsize=3
}

\begin{lstlisting}

for R := 1 to n do
	L--
	L'--
	while not isPal(s[L..R]) do
		L++
	while (L <= L') and  (not isPal(s[L'..R] ) and  (L' <= R) do
		L'++
	c[(L + R) / 2].push(R, 1)
	c[(L' + R) / 2].push(R, 2)
	
\end{lstlisting}

Здесь видно, что внутренние циклы while делают не более $2 n$ увеличений $L$ и $L'$. Таким образом алгоритм линеен. $c$~--- массив, в каждой строчке которого содержится расширяющийся массив. Заметим, что $L + R$ может оказаться нечётным числом (для случая чётного палиндрома), в данном случае мы можем считать, что индексы в массиве c могут быть как целыми, так и полуцелыми числами. 

3. Построим суффиксный массив $sa$ и массив $LCP$. Это можно сделать за линейное время (\cite{PSW}). Напомним, что ячейка $i$ массива $LCP$ равна наибольшему общему префиксу суффиксов $S[sa[i]..n]$ и $S[sa[i - 1]..n]$. 

4. Теперь основываясь на данные первых трёх пунктов, мы можем построить дерево палиндромов за линейное время. 

Известно, что за линейное время можно построить суффиксное дерево по суффиксному массиву. Данный алгоритмы строит сжатый бор всех суффиксов, используя суффиксный массив и массив $LCP$. В данном случае нам нужно построить такой же бор, но из каждого суффикса взять только некоторый его префикс (по длине равный радиусу в этой позиции). При этом мы знаем (из первой главы), что итоговый бор имеет размер $O(n)$, а значит нам не нужно производить сжатие в отличие от суффиксного дерева. 

Итак, рассмотрим модификацию алгоритма, который решает задачу для дерева палиндромов.


\begin{lstlisting}
path := (0)
start := 1
for i := 1 to n do
		k := sa[i]
		start := min(start, lcp[i])
		while path.size() > start do
			path.pop()
		for j := start to r[k] do // этот цикл может оказаться пустым
			path.push( newVertex(path.top(), s[k + j]) )
		for j := 1 to c[k].size() do 
			(num, end) := c[k]
			vertex[num][end] := path[end - k + 1]
\end{lstlisting}

Функция newVertex(v,a) возвращает новую вершину, повешенную к вершине v ребром с меткой a.

Оценим время работы. Внешний цикл, очевидно, работает за линейное время. Нужно оценить внутренние циклы. path.pop() вызовется не больше раз, чем push, значит его можно оценить через push. Этот метод вызовется ровно столько же раз, сколько и newVertex, но мы знаем, что эта функция добавляет вершину в дерево палиндромов, которых не больше $n$. Таким образом первые два цикла суммарно работает не более $O(n)$. Третий работает за суммарную длину $c[k]$ по всем $k$, а эти массивы строились за линейное время, т.е. занимают линейную память. Таким образом алгоритм работает за линейное время.

Этот код нужно запустить дважды: в явном виде (для нечётных палиндромов) и с небольшими модификациями (для чётных палиндромов). После его работы у нас создано дерево палиндромов и для каждого префикса $S[1..i]$  хранится $vertex[1][i]$~--- вершина в дереве, которая является его максимальным суффикс-палиндромом и $vertex[2][i]$~--- второй по величине. 

Очевидно, что после этого суффиксные ссылки мы легко можем посчитать: \\

\begin{lstlisting}
for i := 1 to n do 
	link[ vertex[1][i] ] := vertex[2][i];
	
\end{lstlisting}

Таким образом, мы за $O(n)$ построили дерево палиндромов (включая суффиксные ссылки) в offline для случая, когда алфавит от $1$ до $n$.

\section{Простые примеры задач}

\subsection{Palindromic refrain}
При обучении суффиксным структурам данных (корректное ли понятие?) часто используют следующую задачу: для данной строки $S$ найти строку $P$, максимизирующую величину $|P|*f(S,P)$, где $f(S,P)$~--- число вхождений $P$ в $S$.

Также известна модификация этой задачи, когда $P$ должна быть палиндромом. Задача предлагалась на всеазиатской олимпиаде школьников и подразумевалась авторами, как сложная на комбинациею какой-нибудь суффиксной структуры с алгоритмом Манакера. 
(http://olympiads.kz/apio2014/)

Рассмотрим, как решать данную задачу деревом палиндромов. 

1. Мы знаем, что различных подпалиндромов не более $|S|$, при этом каждому такому подпалиндрому соответствует некоторая подстрока $S$. 

2. Если мы для каждой вершины будем знать число вхождений ($occur$) палиндрома в $S$ , соответствующего ей, то ответом будет максимум по всем вершинам величины $len[v]*occur[v]$. 

Теперь разберёмся, как мы можем посчитать число $occur$. 


Будем считать для каждой вершины вспомогательную величину $occurAsSuffix$, а через неё и посчитаем $occur$. $occurAsSuffix$~--- количество префиксов заданной строки, для которых палиндром, соответствующий данной вершине, является максимальным суффикс-палиндромом. 

При создании вершины, очевидно, $occurAsSuffix$ должна быть равна единице, ведь мы встретили такой палиндром впервые. Далее каждый раз, когда она окажется максимальным суффикс-палиндромом, нужно увеличивать её на единицу. Таким образом, несложно в онлайн поддерживать значение $occurAsSuffix$. К сожалению, с $occur$ всё не так просто, мы не умеем эффективно (за $O(\log|\Sigma|)$) поддерживать его в онлайн, но можем вычислить его за линейное время в оффлайн (т.е. для уже полностью данной строки).

\begin{lemma}
$occur[v]=occurAsSuffix[v]+\sum_{u: link[u]=v} occur[u]$.
\end{lemma}


\proof
Все префиксы данной строки разбиваются на три группы:\\

1. Не имеющие суффикса $v$;

2. Имеющие максимальный суффикс-палиндром $v$;

3. Имеющие суффикс $v$, не являющийся максимальным суффикс-палиндромом

В первом случае нам его не нужно учитывать. Для второго и третьего случая надо просуммировать значения $occurAsSuffix$ по поддереву суффиксных ссылок с корнем $v$. Это можно сделать, например, обходом дерева ссылок снизу вверх:
\qed

\begin{lstlisting}
for v := size to 1 do
	occur[v] := occurAsSuffix[v]
for v := size to 1 do
	occur[ link[v] ] += occur[v]
\end{lstlisting}

$size$~--- размер дерева палиндромов, а значит и номер последней вершины. Для понимания этого кода важно помнить, что суффиксную ссылку мы всегда проводим при создании вершины, а в этот момент вершина, в которую проводится ссылка, всегда уже создана, т.е. имеет меньший номер.

После вычисления $occur$ для всех вершин, $ans = max(occur[v] * len[v])$.

\subsection{Поиск пар палиндромов}
Продолжим изучать возможную дополнительную информацию, которую можно хранить в вершинах. 
Для этого разберём следующую задачу. Дана строка $S$, требуется найти количество троек $i, j, k$ таких, что $1 \leq i \leq j < k \leq |S|$, $S[i..j]$~---палиндром, $S[j + 1..k]$~--- палиндром.

Решение. За $O(n)$ переберём $j$ и решим задачу за $O(1)$ для фиксированного $j$, т.е. найдём число подходящих пар $(i, k)$. Несложно видеть, что ответ на задачу равен произведению числа палиндромов, кончающихся в $j$, на число палиндромов, начинающихся в $j + 1$. Значит нам заранее нужно предпросчитать для каждого символа строки число начинающихся палиндромов и число заканчивающихся. Заметим, что достаточно найти только число заканчивающихся (а после развернуть строку и решить такую же задачу).

Итак, нам для каждого символа нужно найти число палиндромов, заканчивающихся в нём.  Переформулируем задачу: для каждого префикса нужно найти число его суффикс-палиндромов. 

Чтобы найти число суффикс-палиндромов строки, достаточно взять максимальный суффикс-палиндром и выдать количество его суффикс-палиндромов. А т.к. найти максимальный суффикс-палиндром нам позовляет дерево палиндромов, то нам осталось посчитать количество суффикс-палиндромов для каждого подпалиндрома строки, т.е. вершины дерева. Назовём это поле suffCount. 

Несложно понять, что $suffCount[v] = 1 + suffCount[ link[v] ]$, а значит мы можем вычислять его прямо при создании вершины и далее он будет оставаться константой. 

Таким образом, мы решили задачу, использовав дерево палиндромов с одним дополнительным полем в вершине и аналогичное дерево палиндромов для развёрнутой строки.

\subsection{Задача с польского полуфинала}
\textbf{Не знаю, нужна ли эта задача в статье. Для диссертации она вполне подойдёт, т.к. постановка и решение довольно интересные. А для статьи не очень, т.к. всё же довольно надуманная. Поэтому этот кусок я пока не стал завершать.}

Изначально мы имеем пустую строку, далее на каждом шаге мы можем либо приписать символ (слева или справа) к строке, либо развернуть строку и приписать к самой себе справа. 

Требуется для каждого префикса данной строки выдать минимальное число операций, которое нужно для его получения. 

Эта задача предлагалась на студенческом соревновании по алгоритмам, которое является отборочным на международные соревнования (ACM ICPC CERC http://cerc.tcs.uj.edu.pl/ranking/ ). Жюри предложили довольно трудный метод решения задачи. Мы в этом разделе разберём, как с помощью дерева палиндромов решить её совсем легко. 

\textbf{Дорешать}

\section{Поиск подпалиндромов онлайн}
\subsection{Существующие алгоритмы}
Известен линейный алгоритм Манакера (см. \cite{Manacher}) для нахождения всех подпалиндромов в строке. Другая интересная задача~--- нахождение всех \emph{различных} подпалиндромов в строке. Известно, что число различных подпалиндромов не превосходит $n$, где $n$~--- длина строки (см. \cite{DJP}) и известен линейный от $n$ алгоритм нахождения их всех (см. \cite{GPR}). 

В \cite{GPR} была поставлена проблема нахождения оптимального алгоритма, позволяющего за линейное время онлайново посчитать число различных подпалиндромов в каждом префиксе строки. В \cite{KoRuSh} эта задача была решена с использованием алгоритма Манакера (\cite{Manacher}) и алгоритма построения суффиксного дерева (см. \cite{Ukk}) за время $O(n \log |\Sigma|)$ и память $O(n)$, а также была доказана эквивалентность этой задачи одному из видов словарей. Несмотря на хорошую асимптотику, алгоритм имеет недостаток~--- он опирается на две довольно громоздкие структуры. Это отражается и в большом расходе памяти, и в большом и сложном коде. 

В следующем разделе данной главы мы разберём более простую идею решения. Алгоритм на её основе одновременно будет и быстрее работать, и расходовать меньшую память, и иметь меньший размер исходного кода. 

\subsection{Решение деревом палиндромов}
В предыдущем результате у нас было две структуры, каждая из которых решала свою задачу. Первая структура находила наибольший суффикс-палиндром, вторая проверяла, встречается ли этот суффикс как подстрока ранее. Очевидно, что дерево палиндромов имеет необходимый интерфейс для решения данной задачи за то же время.


\section{Общее дерево палиндромов для нескольких строк}

До этого момента мы везде использовали дерево палиндромов, как некоторую структуру, позволяющую хранить все подпалиндромы данной строки. Отметим, что ни рёбра, ни суффиксные ссылки не зависят от конкретных строк. Строка задаёт только множество вершин. 
Вообще говоря, мы можем для данного алфавита взять вообще все палиндромы (которых будет счётное число) и построить дерево палиндромов для них (назовём его общее дерево палиндромов). Дерево палиндромов для любой конечной строки можно получить путём удаления лишних вершин (и инцидентных им рёбер/суффиксных ссылок). 


Пусть нам нужно построить ДП для нескольких строк. Можно поступить следующим образом: для первой строки строим ДП как обычно и проставляем во всех вершинах битовый флаг принадлежности первой строке. Для второй строки ДП строим "поверх" первого: если очередной максимальный суффикс-палиндром уже существует, отмечаем его флагом принадлежности ко второй строке (а если не существует, создаем его как обычно и помечаем флагом). Для третьей и последующих строк строим аналогично. В результате получаем большую экономию места по сравнению с набором отдельных ДП, а также возможность быстро решать некоторые специальные задачи (отметим, что "совместные" суффиксные деревья также строят в подобных целях). Разберем несколько таких задач.



\subsection{Общие подпалиндромы}
Разберём на примере, где мы можем использовать только что полученные знания. 

Задача. Для данных строк $S$ и $P$ определить количество четвёрок $(i, j, k, t)$ таких, что $1 \leq i \leq j \leq |S|$ и $1 \leq k \leq t \leq |P|$, $S[i..j] = P[k..t]$ и $S[i..j]$~--- палиндром. 


Построим общий граф палиндромов для строк $S$ и $P$, и вычислим в его вершинах значения $occur_S$ и $occur_P$ (см. задачу 2.1.).

Теперь несложно видеть, что ответом будет $\sum occur[i] * occur2[i]$.

\begin{remark}
Можно было обойтись и без новой идеи, но тогда нам бы пришлось искать между двух деревьев соответственные вершины, что ощутимо усложняет реализацию и на некоторых текстах повышает используемую память.
\end{remark}

\subsection{Непересекающиеся подпалиндромы}
Для данных строк $S$ и $P$ определить количество строк $T$ таких, что $T$~-палиндром, число вхождений $T$ в $S$ больше числа вхождений $T$ в $P$. 

Решение. Аналогично предыдущей задаче построим общее дерево палиндромов для двух строк и посчитаем $occurS$, $occurP$. В качестве ответа выдадим количество вершин, для которых $occurS > occurP$.

Аналогично можно решить следующие задачи: найти число палиндромов, которые входят во все $k$ данных строк или найти самый длинный, который входит во все $k$ строк. 



\section{Поиск с откатами}
В \textbf{первой} главе мы разобрали алгоритм построения дерева палиндромов с общей оценкой $O(n \log |\Sigma|)$. Но добавление одного символа на некоторых строках может работать за $O(n)$, а в некоторых задачах бывает важна так называемая чистая, неамортизированная оценка. В этой главе речь пойдёт о модификациях дерева палиндромов, которые работают быстро на каждом добавлении нового символа. 

Типичным примером, когда нам нужна чистая оценка, являются задачи, в которых помимо добавления символа, есть его удаление.

Применительно к нашему дереву, у нас помимо $addLetter(c)$ появляется функция $popLetter()$, которая удаляет последний символ. 

Пример. Рассмотрим последовательность: $addLetter('a'), ..., addLetter('a')$  ($n / 3$ раз), $addLetter('b'), popLetter(), addLetter('b'), popLetter(), ..., addLetter('b'), popLetter()$ ($n / 3$ раз). Нетрудно понять, что дерево палиндромов отработает за $O(n^2)$.

В данном разделе мы разберём две модификации дерева, которые позволяют решать задачу с откатами эффективней.

\subsection{Поиск за $O(\log n)$ на шаг}
Рассмотрим пару вершин $(v, link[v])$ в некотором дереве палиндромов. $link[v]$ является суффиксом $v$, рассмотрим символ $c$, который идёт перед $link[v]$ внутри $v$. Теперь проведём дополнительное ребро. Назовём его быстрой ссылкой ($quickLink$). $quickLink[v]$~--- максимальный суффикс-палиндром палиндрома $v$ такой, что символ перед ним не равен символу $c$.

\begin{lemma}
$quickLink$ можно вычислить за $O(1)$ при создании вершины.
\end{lemma}

\begin{lstlisting}

if s[n - len[link[v]]] = s[n - len[link[link[v]]]] then
	quickLink[v] := quickLink[link[v]]
else 
	quickLink[v] := link[v]
	
\end{lstlisting}

Теперь разберёмся, как использовать эти ссылки. Когда мы создаём новую вершину, у нас есть спуск по суффиксным ссылкам в поиске символа $c_2$, который был передан в $addLetter$, перед суффикс-палиндромом. Пусть мы посмотрели по суффиксной ссылке и символ перед ней отличен от $c_2$, тогда мы если мы перейдём по $quickLink$, то точно не пропустим $c_2$ (по определению быстрой ссылки). Значит такой алгоритм будет корректен. 

В нашем алгоритме теперь мы спускаемся по суффиксному пути, но иногда перепрыгиваем через некоторые вершины. Будем называть такой путь быстрым суффиксным путём. Таким образом, новый алгоритм асимптотически не хуже старого.
Значит общая амортизированная оценка сохранилась. Рассмотрим число шагов при добавлении одной конкретной вершины. 


\begin{theorem}

В ДП строки длины $n$ любой быстрый суффиксный путь имеет длину $O(\log n)$
\end{theorem}

Данная теорема является аналагом Лемм 5 и 6 из \cite{KoRuSh2}.

\begin{corollary}
Алгоритм построения графа палиндромов с использованием быстрых суффиксных ссылок тратит $O(\log n)$ времени на добавление одной вершины. 	
\end{corollary}

\subsection{Поиск за $O(\log|\Sigma|)$ на шаг}
В предыдущем разделе мы использовали переход к суффиксу, которому предшествует другой символ. Теперь пойдём дальше в этой идее и укажем еще более быстрый алгоритм, который, правда, требует  $O(log |\Sigma|)$ памяти на каждом шаге. Из каждой вершины сделаем $|\Sigma|$ ссылок, назовём их прямыми ссылками ($directLink[v][c]$). $directLink[v][c]$~--- это максимальный из всех таких суффикс-палиндромов, которым внутри палиндрома $v$ предшествует символ $c$.

\begin{lemma}
Массивы $directLink[v]$ и $directLink[link[v]]$ совпадают во всех позициях, кроме позиции $c$, соответствующей символу, предшествующему $link[v]$ в $v$.
\end{lemma}

При создании вершины мы сначала находим $link$, после чего нам нужно будет заполнить массив $directLink$. Для этого нам достаточно его скопировать за $O(|\Sigma|)$, после чего изменить один символ. 

В основной версии ДП мы вычисляем, куда провести $link$, с помощью спуска по существующим суффиксным ссылкам. При имеющемся $directLink$ мы можем заменить спуск по суффиксным ссылкам на одно обращение к $directLink$.

Понятно, что в данном случае самый затратный по времени шаг~--- это копирование массива. В данном случае нам поможет такая известная структура, как персистентный массив (\cite{PaDi}). От него нам потребуется всего две операции: копирование за $O(1)$ и изменение элемента за логарифмическое время от размера. Правда у него есть неприятный для нас побочный эффект. При каждом присваивании в такой массив мы выделяем дополнительно $O(\log|\Sigma|)$ памяти. Итого на каждый вызов $addLetter$ наша программа будет тратить $O(\log|\Sigma|)$ времени и выделять $O(\log|\Sigma|)$ памяти. По времени это лучше, чем предыдущая реализация, а по памяти хуже. 

\subsection{Возможные реализации и открытый вопрос оптимального решения}

Итак, в этой главе мы рассмотрели некоторые модификации, сейчас мы их подытожим.
В первой главе мы рассмотрели простейший алгоритм, а в этой главе две модификации. Для наглядности ниже приводим таблицу, собирающую все три варианта решений вместе.

\begin{center}
\begin{tabular}{cccc}
Версия & время на $n$ запросов & время на 1 запрос & память на один запрос \\
1 & $\Theta(n \log |\Sigma|)$ & $\Omega(\log|\Sigma|)$, но $O(n)$ & $\Theta(1)$\\
2 & $\Theta(n \log |\Sigma|)$ & $\Omega(\log|\Sigma|)$, но $O(\log n)$ & $\Theta(1)$ \\
3 & $\Theta(n \log |\Sigma|)$ & $\Theta(\log|\Sigma|)$ & $\Theta(\log|\Sigma|)$\\
\end{tabular}
\end{center}

Преимущество первого решения в том, что оно наиболее просто реализуется и имеет минимальную константу по памяти и времени. Второе лучше всего работает, когда размер алфавита и строки одного порядка. Третье хорошо работает, для маленьких алфавитов и очень длинных строк. 

Преимущество второго и третьего в том, что мы можем безболезненно отменить одно действие (оно не очень дорогое), а значит, можем реализовать структуру с откатами или персистентную.

Одно из двух решений позволяет нам выделять не более, чем $O(1)$ памяти на одном шаге. Другое позволяет укладываться в $O(\log|\Sigma|)$ по времени. Отсюда вытекает 

\begin{openproblem}
Существует ли алгоритм построения дерева палиндромов в онлайне, которое на каждом шаге тратит $O(1)$ памяти и $O(\log|\Sigma|)$ ? 
\end{openproblem}

 
\section{Персистентное дерево палиндромов и его применения}
В предыдущих разделах мы изучали дерева палиндромов с откатами. Логичным обобщением структур с откатами являются персистентные структуры. Это структуры, в которых есть возможность адресовать каждый очередной запрос не только к самой структуре, но и к предыдущим версиям этой структуры, при этом каждый изменяющий запрос возвращает новую версию структуры и любая из версий сохраняется в дальнейшем. 


\subsection{Поиск подпалиндромов на боре}

Пусть дано дерево $T$, вершины которого помечены символами; дерево интерпретируется как множество версий некоторой строки (вершине $v$ соответствует строка, читаемая на пути из корня до $v$). Задача состоит в сопоставлении каждой вершине версии ДП для соответствующей строки.
Более конкретно, есть операция $addLetter(v,c)$, которая подвешивает к вершине $v$ новую вершины $u$, помеченную символом $c$; при этом необходимо вычислить версию ДП для вершину $u$.


Как было отмечено в главе 4, если мы хотим хранить деревья палиндромов нескольких строк	, то мы можем построить одно <<общее>> дерево палиндромов, а после этого для каждой строки сохранить список вершин, которые входят в данную строку, после чего вычислить (если нужно в данной задаче) дополнительную информацию. 

В нашей задаче мы через $n$ будем обозначать число запросов $addLetter$, а через $d$ максимальную глубину вершины в боре. 

Мы в каждой вершине бора $i$ будем хранить бинарное сбалансированное дерево поиска, которое будет содержать номера вершин дерева палиндромов, которые содержатся в строке, соответствующей вершине $i$, а также номер вершины, которая соответствует максимальному суффикс-палиндрому $v$. Тогда при создании новой вершины достаточно скопировать бинарное дерево из предка и добавить одно новое состояние. В каждой вершине будет бинарное дерево размером $O(d)$. Для быстрого копирования мы будем использовать персистентное бинарное сбалансированное дерево поиска (\cite{PersStruct}), которое можно скопировать за время $O(\log d)$. 

Теперь рассмотрим базовую реализацию $addLetter$, там из каждой вершины используются $link$, $len$, $go$, которые никак не зависят от конкретных строк. В модифицированных версиях также появились $directLink$ и $quickLink$, которые также не зависят от конкретной строки. От строки зависит только наличие вершины в дереве. Здесь вместо проверки наличия вершины в дереве палиндромов мы будем проверять наличие вершины в бинарном сбалансированном дереве поиска в текущей вершине бора. Тогда если вершины нет в дереве палиндромов, то мы её создадим, перейдём в неё и добавим её в сбалансированное дерево вершины бора. Если вершина есть, то мы перейдём в неё и добавим её в сбалансированное дерево (если её там не было ранее).

\begin{remark}
В данной версии мы не стали реализовывать метод $pop$, т.к. это просто подъём в предка, а эта версия уже сохранена. Реализация этого метода не представляет серьёзных технических проблем.
\end{remark}

\subsection{Подсчёт богатых строк}

Как известно, число различных подпалиндромов строки не превышает длины строки. Те строки, которые имеют в точности $n$ различных подпалиндромов, называются богатыми строками. Джефри Шаллит изучал последовательность чисел (\cite{Shallit}), в которой на $L$ом месте стоит количество бинарных богатых строк длины $L$. Их изучению посвящен ряд работ, см., напр., \cite{GJWZ}.

Комбинаторную сложность языка бинарных богатых строк, т.е. функцию, сопоставляющую числу $L$ количество таких строк длины $L$ ( последовательность A216264 в OEIS \cite{Shallit}). Шаллит вычислил указанную функцию для всех $L\le 25$. С помощью  дерева палиндромов мы продвинулись в вычислениях гораздо дальше~--- до $L=60$, причем вычисления заняли всего $10$ часов работы пользовательского ноутбука.

Для вычисления нам потребуется одна простая лемма. Её доказательство легко следует из того, что при приписывании одного нового символа появляется не более одного нового подпалиндрома. 

\begin{lemma}
Любая подстрока богатой строки также богатая. 
\end{lemma}

Рассмотрим простейшую функцию, реализующую переборное решение, основанное на лемме. 

\begin{lstlisting}
function calcRichString(s)
	ans[|s|]++;
	if isRich(s + '0') and |s| < n 
		calcRichString(s + '0')
	pop()
	if isRich(s + '1') and |s| < n
		calcRichString(s + '1')
	pop()
\end{lstlisting}

Заметим, что внутри каждого конкретного вызова функций выполняется $O(1)$ действий помимо двух вызовов isRich. Кроме того, при каждом вызове $calcRichString$ мы увеличиваем один из элементов массива $ans$, а значит, наше решение работает чем за $O(ANS * T)$, где ANS~--- число различных бинарных богатых слов длины меньше $n$, а $T$~--- время работы одного вызова функции. 

Есть много простых способов проверки на богатство. Все они работают за разное время. Если основываться на результат нашей статьи, то самый простой способ~--- построить для неё дерево палиндромов. Тогда время будет $O(n)$ и суммарное время $O(ANS * n)$.

В данном разделе мы реализуем решение, которое работает в точности за $O(ANS)$.

Для начала немного модифицируем предыдущий код.

\begin{lstlisting}

function calcRichString(L)
	ans[L]++;
	if addLetter('0') and L < n
		calcRichString(L + 1, '0')
	pop()
	if addLetter('1') and L < n
		calcRichString(L + 1, '1')
	pop()
\end{lstlisting}

Он отличается тем, что мы используем версию дерева палиндромов с откатами. В данном случае addLetter приписывает в конец новый символ и сообщает нам, богатое ли слово. Если оно богатое, то мы делаем рекурсивный вызов функции. Далее независимо от того, богато слово или нет, мы откатываем (pop) последнее действие, возвращая слово в исходное состояние. Таким образом мы моделируем обход префиксного дерева всех богатых слов в глубину. Кроме того, мы теперь не передаём строку явно в функцию, чтобы сократить время на передачу параметров до $O(1)$.  

Заметим, что $pop$ реализовать за $O(1)$ легко. Мы не будем в таком случае модифицировать дерево, просто в вершине сделаем пометку (булева переменная), что она не существует, а также нам следует вернуться к максимальному суффикс-палиндрому предыдущей строки. Для этого нам достаточно дополнительно хранить стек максимальных максимальных суффикс-палиндромов всех префиксов строки и сделать pop из этого стека.

Теперь разберёмся с $addLetter$. Мы будем использовать реализацию 3. В ней выделяемая память и время на шаг равны $\Theta(\log |\Sigma|)$, но в нашем случае алфавит бинарный, что влечёт константное время выполнения на шаг (как и память). 

Заметим также, что для бинарного алфавита нам не нужно использовать персистентный массив, достаточно обычного массива.

Итого функции $addLetter, pop$ работают за $O(1)$, давая общую асимптотику $O(ANS)$.

\begin{remark}
Описанный выше алгоритм позволяет за разумное время вычислить комбинаторную сложность для $L=58$. Чтобы дойти до $L=60$, мы использовали различные неасимптотические оптимизации, сокращающие константу времени выполнения. Реализацию можно посмотреть здесь: (\textbf{ссылка})
\end{remark}

\section{Задача о разбиении на подпалиндромы}

. В [6] приведено решение этой задачи за время O(..), которое затем при помощи битового сжатия доведено до асимптотики O(kn).

В \cite{GalilSeiferas} была поставлена задача о разбиении строки на $k$ палиндромов для произвольного значения параметра $k$. В \cite{KoRuSh2} приведено решение этой задачи за время $O(k n \log n)$, которое затем при помощи битового сжатия доведено до асимптотики $O(kn)$. В данной статье мы сфокусируемся на построении решения, не зависящего от $k$.

\begin{remark}
В \cite{Ravsky} показано, что для случайной строки математическое ожидание минимального $k$ является $\Omega(n)$. Для таких строк решение за $O(nk)$ неприемлимо.
\end{remark}


\subsection{Разбиения на минимальное даёт разбиение на k}
\begin{remark}
Если дано разбиение строки длины $n$ на $k$ палиндромов, то за время $O(n)$  можно получить разбиение строки на $k+2t$ палиндромов для любого натурального $t$ такого, что $k+2t\leq n$.

\end{remark}

\proof
Мы будем считать, что в разбиении есть хотя бы два палиндрома не единичной длины, т.к. другой случай прост и не представляет интереса. 

Возьмём самый большой палиндром в разложении. Если его длина больше двух, то мы отрежем с его концов по одному символу и получим три палиндрома вместо одного. Т.е. увеличим число палиндромов в разбиении на два. Если же все палиндромы не длинней двух, то возьмём два палиндрома длины два и разрежем, получив на два больше палиндрома в разложении.

\qed

Таким образом, задача разбиения на $k$ палиндромов сводится к решению двух похожих задач: разбить строку на минимальное четное число палиндромов и на минимальное нечетное число палиндромов. Ниже мы покажем, как сделать это при помощи дерева палиндромов.


\subsection{Решение задачи о разбиении на минимальное число палиндромов с помощью дерева}
В данном разделе мы приведём онлайновый алгоритм, решающий задачу разбиения строки на минимальное число палиндромов за время $O(n \log n)$. 

Заметим, что существует другое решение этой задачи, работающее также за $O(n \log n)$, оно приведено в \cite{Fici}. Наше решение асимптотически такое же по времени, но использует другой подход. На наш взгляд, наше решение проще с точки зрения реализации и уменьшает количество потенциально возможных ошибок.

Для решения задачи мы будем вычислять массив $ans$, где $ans[i]$~--- минимальное число палиндромов, на которое разбивается строка $s[1..i]$. Очевидно, что для вычисления ответа $ans[i]$ за линейное время, нам достаточно перебрать все суффикс-палиндромы и взять минимум из чисел, находящихся в $ans$ на местах, непосредственно предшествующих началам этих суффикс-палиндромов, и добавить к нему единицу. 

Таким образом, $ans[i]=1+\min_{s[j+1..i]\in Pal} ans[j]$.

Для данной задачи нам понадобится в каждой вершине дерева палиндромов хранить две дополнительные величины: разность ($diff$) и серийную ссылку ($seriesLink$). 

Итак, определим оба поля. $diff[v] = len[v] - len[link[v]]$. Т.е. разница длин данного палиндрома и его максимального суффикс-палиндрома. $seriesLink[v]$~--- это вершина в суффиксном пути $v$, имеющая максимальный длиной среди тех, разность которых отлична от $diff[v]$. Таким образом, $seriesLink[v]$~--- это суффиксная ссылка, которая оптом пропускает все вершины (серию палиндромов) с разностью $diff[v]$. 

Более строго определим серию палиндромов. Назовём серией $v$~--- последовательность вершин в суффиксном пути $v$ от $v$ (включительно) до $seriesLink[v]$ (не включительно).

Для большей наглядности покажем код, который вычисляет серийную ссылку. 

\begin{lstlisting}

if diff[v] = diff[link[v]] then 
	seriesLink[v] := seriesLink[link[v]]
else 
	seriesLink[v] := link[v]

\end{lstlisting}

Таким образом, обе эти величины вычисляются при создании вершины, используя $O(1)$ времени и $O(1)$ дополнительной памяти.

\begin{remark}
Можно заметить, что $seriesLink$ очень похожа на $quickLink$. Для целей данного раздела нам не подойдёт $quickLink$, но несложно понять, почему вместо $quickLink$мы всегда можем использовать $seriesLink$ без ухудшения асимптотики.
\end{remark}

Рассмотрим наивную реализацию, вычисляющую за линейное время значение $ans[n]$.
\begin{lstlisting}
for (v = maxPal; len[v] > 0; v = link[v])
	ans[n] = min(ans[n], ans[n - len[v]] + 1)
\end{lstlisting}


Теперь используем серийные ссылки и реализуем алгоритм за то же время.
\begin{lstlisting}
for (v = maxPal; len[v] > 0; v = seriesLink[v])
	ans[n] = min(ans[n], getMin(v))
\end{lstlisting}

Функция getMin(u) принимает на вход вершину в дереве. 
\begin{lstlisting}
function getMin(u)
	res := INF
	for (v := u; v > seriesLink[a]; v := link[v])
		res := min(res, ans[n -	 len[v]] + 1)
	return res
\end{lstlisting}

Функция getMin в худшем случае будет работать за линейное время. Мы по сути по-другому переписали предыдущий код. Сразу же опишем реализацию $getMin$ для случая серии из одного элемента.

\begin{lstlisting}
function getMin(a)
	if diff[a] = diff[link[a]] // в серии более одного элемента?
		???
	else
		return ans[n - len[a]] + 1
\end{lstlisting}

 В дальнейшем будем работать только с сериями из более, чем одного элемента. Для работы нам потребуется три вспомогательные леммы.

\begin{lemma}
Пусть для данной строки $s[1..n]$ палиндром $v$~--- максимальный в некоторой серии, т.е. следующий по возрастанию длины палиндром имеет другой $diff$. И $diff[v] = diff[link[v]]$, т.е. в серии более одного элемента. Тогда предыдущее вхождение $link[v]$ в строку было на $diff[v]$ левее текущего.
\end{lemma}

\begin{lemma}
Пусть для данной строки $s[1..n]$ палиндром $v$~--- максимальный в некоторой серии. И $diff[v] = diff[link[v]]$. Тогда в строке $s[1..n-diff[v]]$ палиндром $link[v]$ является максимальным в серии.
\end{lemma}

\begin{lemma}
Длина пути по серийным ссылкам имеет порядок $O(\log n)$.
\end{lemma}

\begin{corollary}
Из предыдущей леммы следует, что мы делаем $O(\log n)$ вызовов функции $getMin$. 
\end{corollary}

Учитывая следствие, реализовав $getMin$ за $O(1)$, мы решим задачу за $O(\log n)$ на шаг.

Обозначим на изображении всю серию $v$, на изображении ниже~--- серию предыдущего вхождения $link[v]$. Напомним, что мы работаем со случаем $diff[v] = diff[link[v]]$.

\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{series.jpg}
\end{figure}

На рисунке видно, что их левые границы совпадают везде, кроме одной позиции. 
Поскольку ссылка из $v$ ведёт в $link[v]$, количество элементов в серии $v$ ровно на единицу больше. Первые их позиции совпадают, т.к. $link[v]$ является префиксом $v$, а последующие ввиду равенства $diff$ в этих сериях. 

Отсюда видно, что $diff[v]$ шагов назад мы уже считали минимум из всех нужных чисел, кроме одного. Значит нам нужно было его тогда запомнить, чтоб сейчас использовать. Мы можем это сделать прямо внутри функции $getMin$, т.к. $link[v]$ встретился в прошлый раз $diff[v]$ шагов назад (по лемме 6), причём являлся на том шаге максимальным в своей серии (по лемме 7). Нам по сути до возвращения теперь достаточно сохранить старое значение в вершине дерева палиндромов. Мы можем сделать это так для текущей реализации:

\begin{lstlisting}
function getMin(a)
	if diff[a] = diff[link[a]] // в серии более одного элемента?
		???
	else
		 dp[a] = ans[n - len[a]]
	return dp[a] + 1
\end{lstlisting}

Осталось заполнить случай невырожденной серии. Как мы показали выше, все кроме одного значения посчитаны в $dp[link[v]]$. Оставшийся суффикс-палиндром находится перед последним палиндромом в серии. Мы легко можем вычислить длину первого палиндрома в следующей серии, она равна $len[seriesLink[v]]$, а чтоб взять предыдущий, достаточно прибавить $diff[v]$. Итого нас интересует позиция $n - (len[seriesLink[v]] + diff[v])$. Значит итоговый код выглядит так:


\begin{lstlisting}
function getMin(a)
	if diff[a] = diff[link[a]] // в серии более одного элемента?
		dp[a] = min(ans[n - (len[seriesLink[v]] + diff[v])], dp[link[a]])
	else
		dp[a] = ans[n - len[a]]
	return dp[a] + 1
\end{lstlisting}

Во втором случае $n - len[a]$~--- позиция перед последним элементом в серии. А значит мы можем переписать (для единообразия) код так:

\begin{lstlisting}
function getMin(a)
	if diff[a] = diff[link[a]] // в серии более одного элемента?
		dp[n] = min(ans[n - (len[seriesLink[v]] + diff[v])], dp[link[a]])
	else
		dp[n] = ans[n - (len[seriesLink[v]] + diff[v])]
	return dp[n] + 1
\end{lstlisting}

Ну а теперь уже видно, что последний элемент можно вынести за if. Получаем такой итоговый код функции:

\begin{lstlisting}
function getMin(a)
	dp[a] = ans[n - (len[seriesLink[v]] + diff[v])] // последний элемент в серии
	if diff[v] = diff[link[v]] then
		dp[a] = min(dp[a], dp[link[a]])
	return dp[a] + 1
\end{lstlisting}




\subsection{Гипотеза о линейном решении}
Итак, мы имеем алгоритм, который разбивает строку на минимальное число палиндромов за $O(n \log n)$, из них затрачивает на построение дерева палиндромов $O(n \log |\Sigma|)$. 
В оффлайновой версии мы можем построить дерево заранее за $O(n)$, после чего всё равно за $O(n \log n)$ найти разбиение.

В \cite{KoRuSh2} алгоритм, работающий за $O(k n \log n)$ был оптимизирован до $O(kn)$ с помощью метода четырёх русских.

В том алгоритме вычислялась битовая матрица $k\times n$ из флагов, указывающих на разбиваемость префиксов строки на заданное число палиндромов, поэтому такой метод ускорения был естественным. В нашей задаче мы работаем с массивом целых чисел, поэтому здесь непосредственное применение метода четырёх русских невозможно. 

\begin{theorem}

Пусть $S$~--- строка, $c$~--- символ. Если минимальное число палиндромов, на которое можно разбить $S$, равно $k$, то  минимальное число палиндромов, на которое можно разбить $Sc$, равно $k-1, k$ или $k+1$.
\end{theorem}

\proof
1. Очевидно, что мы всегда можем получить $k + 1$, для этого достаточно взять разбиение предыдущей строки и добавить в разбиение один новый символ. Значит ответ будет не более $k + 1$.

2. От противного. Допустим минимальный ответ для новой строки равен $t$ и $t < k - 1$. Тогда возьмём последний палиндром в разбиении. Если его длина больше двух, то мы можем разделить его на три палиндрома (первый символ, последний символ, центральная часть). Тогда видно, что для предыдущей строки существует разбиение из $t + 1$, $t + 1 < k$, получили противоречие. Если его длина равна двум или единице, то для меньшей строки будет существовать разбиение $t$ и $t - 1$ соотвественно, что аналогично приводит к противоречию. 

\qed

Теперь рассмотрим битовую матрицу $n$ на $n$. В ячейке $(i, j)$ будет располагаться единица в случае, если префикс длины $i$ можно разбить на $j$ палиндромов, ноль иначе. Теперь вспомним, что проверять в каждой строке нам нужно только три числа ($k-1, k, k + 1$, где $k$~--- минимальное разбиение с предыдущего шага). Для каждого из них нам нужно взять битовый $or$ от $\log n$ битовых значений. Т.е. всего $3 n \log n$ битовых операций. Если бы такие операции у нас были бы сгруппированны одним большим блоком, то мы методом четырёх русских выполнили бы их за $3 n $ действий. Отсюда

\begin{con}
Используя Теорему 2, дерево палиндромов и метод четырёх русских, можно решить задачу о разбиении на минимальное число палиндромов и о разбиении на $k$ палиндромов за $O(n\log|\Sigma|)$ в онлайне и $O(n)$ в оффлайне. 
\end{con}

\section{Итоги}

В данной статье мы разобрали дерево палиндромов. Рассмотрели его различные модификации, которые более эффективны в использовании времени, либо памяти. Одна из модификаций позволяет сделать дерево палиндромов с откатами, другая делает его персистентным. Разобрали множество возможных применений. Самыми существенными из них являются: простая реализация разбиения строки на палиндромы, поиск богатых бинарных строк, а также поиск подпалиндромов строки.

В статье поставлена гипотеза о возможности линейного поиска разбиения на минимальное число подпалиндромов, а также сформулирована открытая проблема реализации оптимального дерева палиндромов.


\bigskip

\bibliography{paltree}

\end{document}
